package com.arron.algorithm.leetcodetop100.回溯;

import java.util.Arrays;
import java.util.HashMap;
import java.util.Map;

public class 划分为k个相等的子集 {


    Map<String,Boolean> memMap;

    public boolean canPartitionKSubsets(int[] nums, int k) {


        if (nums.length<k){
            return false;
        }

        int sum =Arrays.stream(nums).sum();


        if (sum %k !=0){
            return false;
        }
        int[] used = new int[nums.length];
        memMap = new HashMap<>();
        //每个桶应该装多少值
        int target = sum/k;
        Arrays.sort(nums);

        int left = 0;
        int right = nums.length-1;

        while (left < right){

            int temp = nums[left];
            nums[left] = nums[right];
            nums[right] = temp;
            left++;
            right--;
        }


        return dfs(nums,k,target,0,0,used);
    }



    //数字装进 k 个桶的角度进行穷举
    // 以桶的视角进行穷举数字

    /**
     *
     * @param nums
     * @param k 第k个桶
     * @param target 每个桶应该装多少
     * @param sum 当前桶装了多少
     * @param used 哪些数字已经装过了
     * @return
     */
    public boolean  dfs(int[] nums,int k,int target,int start,int sum,int[] used){

        if (k==0){
            //桶装完了，还没跳出直接返回true
            return true;
        }
        String path = Arrays.toString(used);

        if (memMap.containsKey(path)){
           return memMap.get(path);
        }



        if (sum == target){

            //这个桶装满了进入下一个桶
            k--;
            boolean state = dfs(nums, k, target, 0, 0, used);
            //将第k个桶的装满的选择路径记录下来，下次别的桶就不会再选了
            memMap.put(path,state);
            return state;
        }



        for (int i = start; i < nums.length; i++) {

            if (used[i]!=0){
                continue;
            }

            if (sum+nums[i]> target){
                continue;
            }


            sum += nums[i];
            used[i] = 1;
            //递归穷举下一个数字装入桶中
            if (dfs(nums,k,target,i+1,sum,used)){
                return true;
            }

            sum-=nums[i];
            used[i] =0;

        }
        return false;
    }

    public static void main(String[] args) {

        int[] a= {1,0,1};
        System.out.println(Arrays.toString(a));

    }




}
